import java.lang.reflect.ParameterizedType;
import java.util.*;

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//
public class Sort {
    public Sort() {
    }

    public static void mergeSort1(int[] array) {
        mergeSortDivide(array, 0, array.length - 1);
    }

    private static void mergeSortDivide(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSortDivide(array, left, mid);
            mergeSortDivide(array, mid + 1, right);
            merge(array, left, right, mid);
        }
    }

    private static void merge(int[] array, int start, int end, int mid) {
        int s1 = start;
        int s2 = mid + 1;
        int[] tmp = new int[end - start + 1];
        int var7 = 0;

        while (s1 <= mid && s2 <= end) {
            if (array[s1] <= array[s2]) {
                tmp[var7++] = array[s1++];
            } else {
                tmp[var7++] = array[s2++];
            }
        }

        while (s1 <= mid) {
            tmp[var7++] = array[s1++];
        }

        while (s2 <= end) {
            tmp[var7++] = array[s2++];
        }

        for (int i = 0; i < tmp.length; ++i) {
            array[i + start] = tmp[i];
        }

    }

    //直接插入排序
    public static void insertSort(int[] arr) {
        //代码可以从i = 1开始算起，但是做题画图时，一定要从i = 0开始算起
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            int tmp = arr[i];
            for (; j >= 0; j--) {
                //如果arr[j] > tmp变成arr[j] >= tmp就变成不稳定了
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }


    //折半插入排序
    public static void bsInsertSort(int[] arr) {
        //代码可以从i = 1开始算起，但是做题画图时，一定要从i = 0开始算起
        for (int i = 1; i < arr.length; i++) {
            int v = arr[i];
            int left = 0;//左边标记永远从0下标开始
            int right = i;
            while (left < right) {
                int mid = (left + right) / 2;
                //需要[left right)
                if (arr[mid] < v) {
                    //如果区间要闭，就赋值mid + 1或者mid - 1
                    left = mid + 1;
                } else {
                    //如果右区间要开，就赋值mid
                    right = mid;
                }
            }

            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = v;
        }
    }

    //希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array, gap);
            gap /= 2;//增量是多少都可以，随便小伙伴们写
        }
        shell(array, 1);
    }

    //有增量的直接插入排序
    //不是一组希尔排序全部排完，是间隔性的，可能是第一组先插一个，第二组再插一个，第一组再插……
    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > array[j + gap]) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    //选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            int j = i + 1;
            int minIndex = i;
            for (; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                    flag = true;
                }
            }
            if (flag) {
                int tmp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = tmp;
            }
        }
    }

    //双向选择排序
    //和单向的时间复杂度一致，可能只是更帅一点吧
    public static void selectSortOP(int[] array) {
        int low = 0;
        int high = array.length - 1;
        // [low, high] 表示整个无序区间
        // 无序区间内只有一个数也可以停止排序了
        while (low < high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (array[i] < array[min]) {
                    min = i;
                }
                if (array[i] > array[max]) {
                    max = i;
                }
            }
            swap(array, low, min);
            //见下面解析：最大值可能在low的位置上，min和low一交换，最大值就到了min的位置
            if (max == low) {
                max = min;
            }
            swap(array, high, max);
            low++;
            high--;
        }
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //堆排序（大根堆）
    //从上往下建堆，所以先找父节点，再找孩子结点
    public static void createHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    //向下调整
    public static void shiftDown(int[] array, int parent, int len) {
        //定义一个记录孩子下标的变量（左孩子）
        int child = 2 * parent + 1;
        //判断父节点和孩子结点的大小，至少左孩子要存在
        while (child < len) {
            //比较左右孩子
            if ((child + 1) < len && array[child] < array[child + 1]) {
                child++;
            }
            //判断父节点和孩子节点
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //开始排序：堆排序分为三个功能 ①开始建堆，②交换，③向下调整，重复②和③步
    public static void heapSort(int[] array, int len) {
        int end = len - 1;//确定最后一个结点的下标
        createHeap(array);//建堆
        //当只剩下一个结点的时候，就不需要交换
        while (end > 0) {
            //交换
            swap(array, 0, end);
            //向下调整
            shiftDown(array, 0, end);
            //调整完一个结点，下一个
            end--;
        }
    }

    //计数排序
    public static void countSort(int[] array) {
        //1. 找到待排序数组的范围，也就是找到最大值和最小值
        int max = array[0];
        int min = array[0];
        //循环遍历找寻最小值和最大值
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max)
                max = array[i];
            if (array[i] < min)
                min = array[i];
        }
        //计算待排数组的长度
        int len = max - min + 1;
        //2. 定义一个计数数组
        int[] count = new int[len];
        //3. 遍历array数组，把数据计数到计数数组中
        for (int i = 0; i < array.length; i++) {
            count[array[i] - min]++;
        }
        //4. 将array数组还原
        int index = 0;//来控制array数组的下标
        for (int i = 0; i < array.length; i++) {
            //这个循环的作用，是把count里面标记的数据取出来
            while (count[i] > 0) {
                array[index] = i + min;
                index++;
                count[i]--;
            }
        }
    }

    public static void radixSort(int[] array) {
        //1. 先确定最大值，方便后期遍历
        int max = 0;
        for (int x : array) {
            max = Math.max(max, x);
        }
        //2. 创建队列，因为我们这里是四10个数字，所以创建10个队列，使用LinkedList来代替队列
        Queue<Integer>[] queueList = new LinkedList[10];
        //为里面的元素赋值，给一个队列
        for (int i = 0; i < queueList.length; i++) {
            queueList[i] = new LinkedList<>();
        }

        //3. 开始分类和收集
        /*
        123 / 1(divider) % 10 = 3
        123 / 10(divider) % 10 = 2
        123 / 100(divider) % 10 = 1
         */
        //最大值的作用体现了，限制了divider的移动
        //divider不断地往1,10,100直至大于max扩大
        for (int divider = 1; divider <= max; divider *= 10) {
            //3.1 分桶（也是分类）
            for (int x : array) {
                int index = x / divider % 10;
                queueList[index].offer(x);
            }
            //3.2 收集（还原原来数组）
            int i = 0;//定义原来数组的下标
            for (Queue<Integer> queue1 : queueList) {
                while (queue1.peek() != null) {
                    array[i] = queue1.poll();
                    i++;
                }
            }
        }
    }



    /*
    时间复杂度：
        最好情况是：O(NlogN) 均匀分割待排序列，尽量满二叉树
        最坏情况是：O(N^2)，有序或者逆序，单分支的树
    空间复杂度：
        最好情况是：O(logN) 树的高度，把持着mid变量
        最坏情况是：O(N)，有序或者逆序，单分支的树
    稳定性：不稳定
     */
    //这里为了统一其他排序算法的接口，所以只传一个参数——数组
    public static void quickSort(int[] array) {

        quick(array, 0, array.length - 1);
    }

    //划分
    private static void quick(int[] array, int start, int end) {
        //这里为什么是>=，因为防止end到了start后面，导致越届
/*
        s e
        mid
    例如：1 2
        再递归进去，end == -1，start == 0，所以必须交 =
 */
        if (start >= end) {
            return;
        }

        //优化二：
        if(end - start + 1 <= 14){
            insertSort2(array,start,end);
        }
        //优化一：
        //排序，返回到最终位置的元素下标
        int index = midThree(array,start,end);
        swap(array,start,index);
        int mid = partition3(array, start, end);
        //递归左边
        quick(array, start, mid - 1);
        //递归右边
        quick(array, mid + 1, end);
    }

    //第一种：快速排序，挖坑法，无优化版本
    //每一趟的操作，交换，填坑
    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];//保存最左位置的值
        //开始找坑
        //多次左右走
        while (left < right) {
            //先右往左走，找一个值比tmp小的，一次循环或者说一次向右走
            // 这里必须要是 >= ，不然当下标0和下标array.length的话，就会陷入死循环，这两个下标的值一直在交换
            //提问：为什么不需要再次++，去进入循环呢？
            while (left < right && array[right] >= tmp)
                right--;
            array[left] = array[right];
            //从左往右走，找一个值比tmp大的，一次循环或者说一次向左走
            while (left < right && array[left] <= tmp)
                left++;
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //第二种快速排序，Hoare法，主要是交换的方式不同
    private static int partition2(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;//把left开始的下标保存起来先
        while (left < right) {
/*
为什么不能先走左呢？
答：因为先走左的话，最后right会停在比mid大的值的下标，left找到right停下来，交换i和left的值，导致不满足快排的结果
 */
            //这两个循环，永远是right追left
            while (left < right && array[right] >= tmp)
                right--;
            while (left < right && array[left] <= tmp)
                left++;
            swap(array, left, right);//自定义的交换方法
        }
        swap(array, i, left);
        return left;
    }

    //第三种排序算法：前后指针法
    //写法一
    private static int partition3(int[] array, int left, int right) {
        int cur = left;//prev记录的是最后一位比array[left]的下标
        int prev = left + 1;
        while (cur <= right) {
            if (array[prev] < array[left] && array[++cur] != array[prev]) {
                swap(array, prev, cur);
            }
            prev++;
        }
        swap(array, left, cur);
        return cur;
    }

    //优化的方案，均匀的分割！三数取中法
    private static int midThree(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if(array[left] > array[right]){
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
        }else{
            //array[right] > array[left]
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    //直接插入排序
    public static void insertSort2(int[] arr,int left,int right) {
        //代码可以从i = 1开始算起，但是做题画图时，一定要从i = 0开始算起
        for (int i = left + 1; i < arr.length; i++) {
            int j = i - 1;
            int tmp = arr[i];
            for (; j >= left; j--) {
                //如果arr[j] > tmp变成arr[j] >= tmp就变成不稳定了
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    //非递归实现快速排序
    //用栈实现
    public static void quickSort2(int[] array){
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length - 1;
        int mid = partition1(array,left,right);
        if(mid > left + 1){
            stack.push(left);
            stack.push(mid - 1);
        }
        if(mid < right - 1){
            stack.push(mid + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            mid = partition1(array,left,right);
            if(mid > left + 1){
                stack.push(left);
                stack.push(mid - 1);
            }
            if(mid < right - 1) {
                stack.push(mid + 1);
                stack.push(right);
            }
        }
    }

}

